Linear Feedback Shift Registers (LFSR) are used in digital communication and other systems for data processing such as, for example, ciphering, error detecting, error correcting, or for generating pseudo random sequences. In an LFSR, a plurality of stages is coupled for sequential propagation of signals through the stages. The signal propagation can be influenced by exclusive-or-gates (xor-gates) arranged according to characteristic polynomials of an input-output function.
The theoretical background for using LFSRs in, e.g., a message encoder, is explained in chapter 5.6. of Sklar, B.: Digital Communications, Fundamentals and Applications, Prentice Hall, Englewood Cliffs, N.J., ISBN 0-13-211939-0 [1].
LFSRs can be classified into TYPE 1 and TYPE 2. This classification has been explained U.S. Pat. No. 5,073,909 to Kotzin et. al. [2] in reference to LFSR which are used to generate random sequences. LFSRs which read input signal IN and provide output signal OUT are now explained by way of example in FIGS. 1-2. FIG. 1 shows prior art LFSR 100 of TYPE 1. LFSR 100 comprises stages 111, 112, 113, 114 and xor-gates 115 and 116. IN is supplied to xor-gate 115 and then propagated through stages 111-114. OUT is available at the output of stage 114. Signal T1, obtained from xor-gate 116 acting upon the outputs of stages 113 and 114. T1 is then fed back to the input of stage 111 through xor-gate 15. TYPE 1, as used herein, defines an LFSR wherein the various stages (e.g., 111-114) are cascaded together, input to output, without interruption by an intervening signal (e.g., T1). TYPE 1 LFSRs are commonly used to implement algorithms for, e.g., the generation of a mask set sequence for data ciphering.
FIG. 2 shows prior art LFSR 200 of TYPE 2. LFSR 200 comprises stages 221, 222, 223, 224, and xor-gates 225 and 226. IN is supplied to xor-gate 225 and then propagated through stage 221, xor-gate 226, and stages 222-224. OUT is available at the output of stage 224. Xor-gate 226 performs an exclusive-or operation on the outputs of stages 221 and 224. This operation is then used to determine the state of stage 222.
Finally, the output of stage 224 is fed back to xor-gate 225. TYPE 2, as used herein, defines an LFSR wherein the various stages (e.g., 221-224) are cascaded together, however, the shift path is interrupted by the introduction of a signal (e.g., T2). TYPE 2 LFSRs are commonly used to implement algorithms for e.g., for parity code generation, error detection and error correction.
As is used herein and only for the convenience of explanation, a first direction is defined for signals going from elements (stages or xor-gates) with low reference numbers (e.g., 111) to elements with higher reference numbers (e.g., 114). A second direction is defined in the opposite way. As shown in the figures, the first direction goes from left to right and the second direction goes from right to left. For example, in FIG. 1, IN goes in first direction to OUT, T1 goes in second direction from xor-gate 116 to xor-gate 115. T1 can therefore be considered as feedback signal. Although the term LFSR implies feeding "back" signals (e.g., T1, T2 of FIGS. 1-2), LFSRs as discussed here can also feed forward signals.
In LFSRs 100 and 200 as shown in FIGS. 1-2, the stages and xor-gates are hard wired so that the characteristic polynomials of the LFSR can not be changed. However, there are instances in circuit design where one application (e.g., a cellular phone) needs variable characteristic polynomials. Operators for phone systems may use their own proprietary polynomials for e.g., data ciphering. It is easier to market phones having similar hardware but different software than market phones having different hardware. Further, some applications require different data processing algorithms at different times. In view of hardware expenses and power consumption, it is not convenient to have separate LFSRs (TYPEs 1 and 2) for different algorithms. There is a need to design a LFSR able to provide both TYPE 1 and TYPE 2 features.
FIG. 4 of U.S. Pat. No. 5,446,683 to Mullen et. al. [1] shows an LFSR incorporating provisions for variation of the characteristic polynomial. However, the LFSR is of TYPE 1 and cannot be reconfigured to TYPE 2. The present invention seeks to provide a fully programmable LFSR with variable characteristic polynomials which is switchable between TYPE 1 and TYPE 2.